/*
 * p1006.cpp
 *
 *  Created on: 2013-7-25
 *      Author: zy
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 50005;
const int INF = 0x7fffffff;
int g[maxn][4];
int value[maxn];
int trap[maxn];
int n, c;
vector<int> son[maxn];
struct node
{
	int val;
	int son;
} dp[maxn][4][2];
void init()
{
	for (int i = 0; i <= n; i++)
		son[i].clear();
	memset(dp, 0, sizeof(dp));
	memset(g, 0, sizeof(g));
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &value[i], &trap[i]);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x++;
		y++;
		son[x].push_back(y);
		son[y].push_back(x);
	}

}
void dfs(int u, int pa)
{
	for (int i = 0; i < son[u].size(); i++)
	{
		int v = son[u][i];
		if (v == pa)
			continue;
		dfs(v, u);
		for (int j = 0; j < c; j++)//j表示子节点v之前走过的trap
		{
			if (dp[u][j + trap[v]][0].val < dp[v][j][0].val + value[v])
			{
				dp[u][j + trap[v]][1].val = dp[u][j + trap[v]][0].val;
				dp[u][j + trap[v]][0].val = dp[v][j][0].val + value[v];
				dp[u][j + trap[v]][0].son = v;
			}
			else if (dp[u][j + trap[v]][1].val < dp[v][j][0].val + value[v])
				dp[u][j + trap[v]][1].val = dp[v][j][0].val + value[v];
		}

	}
}
void dfs2(int u, int pa)
{
	if (pa != -1)
	{
		for (int j = 0; j < c; j++)
			if (dp[pa][j][0].son != u)
				g[u][j + trap[pa]] = max(g[pa][j], dp[pa][j][0].val)
						+ value[pa];
			else
				g[u][j + trap[pa]] = max(g[pa][j], dp[pa][j][1].val)
						+ value[pa];

	}
	for (int i = 0; i < son[u].size(); i++)
	{
		int v = son[u][i];
		if (v != pa)
			dfs2(v, u);
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &n, &c);
		init();
		dfs(1, -1);
		dfs2(1, -1);
		int ans = -INF;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < c; j++)
				ans = max(ans, max(dp[i][j][0].val, g[i][j]) + value[i]);
		cout << ans << endl;
	}

	return 0;
}
